import collections


class Solution(object):
    def sequenceReconstruction(self, nums, sequences):
        """
        :type nums: List[int]
        :type sequences: List[List[int]]
        :rtype: bool
        """
        n = len(nums)
        d = {i + 1: 0 for i in range(n)}
        edge = collections.defaultdict(set)
        for item in sequences:
            for i in range(len(item) - 1):
                if 1 <= item[i] <= n and 1 <= item[i + 1] <= n:
                    if item[i + 1] not in edge[item[i]]:
                        edge[item[i]].add(item[i + 1])
                        d[item[i + 1]] += 1
                else:
                    return False
        now_count = 0
        for key in d:
            if d[key] == 0:
                index = key
                now_count += 1
        if now_count != 1:
            return False
        out = [index]
        while now_count == 1:
            now_count = 0
            next_index = index
            for item in edge[index]:
                d[item] -= 1
                if d[item] == 0:
                    next_index = item
                    out.append(item)
                    now_count += 1
            index = next_index
        if now_count >= 2:
            return False
        else:
            return out == nums


data = Solution()
nums = [4, 1, 5, 2, 6, 3]
sequences = [[5, 2, 6, 3], [4, 1, 5, 2]]
print(data.sequenceReconstruction(nums, sequences))
nums = [1, 2, 3]
sequences = [[1, 2], [1, 3]]
print(data.sequenceReconstruction(nums, sequences))
nums = [1, 2, 3]
sequences = [[1, 2]]
print(data.sequenceReconstruction(nums, sequences))
nums = [1, 2, 3]
sequences = [[1, 2], [1, 3], [2, 3]]
print(data.sequenceReconstruction(nums, sequences))
nums = [1]
sequences = [[1]]
print(data.sequenceReconstruction(nums, sequences))